package 算法;

import java.util.ArrayList;

/**
 * @author zhangmin
 * @create 2021-12-06 11:46
 * 搜索算法
 */
public class Search01 {
    /**==============================================================================================================================================
     * JZ53 数字在升序数组中出现的次数
     * 给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数
     * 1、直接统计
     * 2、二分查找左右边界。
     * */
    public int GetNumberOfK1(int [] array , int k) {
        if (array.length==0)return 0;
        int i=0,count=0;
        while (i<array.length&&array[i]<k)i++;
        for (int j = i; j < array.length; j++) {
            if (array[j]==k) count++;
            else break;
        }
        return count;
    }
    private int left_bound(int[] arr,int k){
        int left=0,right=arr.length-1;
        while (left<=right){
            int mid=left+(right-left)/2;
            if (arr[mid]<k){
                left=mid+1;
            }else if (arr[mid]==k){
                right=mid-1;
            }else {
                right=mid-1;
            }
        }
        return left;
    }
    private int rigth_bound(int[] arr,int k){
        int left=0,right=arr.length-1;
        while (left<=right){
            int mid=left+(right-left)/2;
            if (arr[mid]<k){
                left=mid+1;
            }else if (arr[mid]==k){
                left=mid+1;
            }else {
                right=mid-1;
            }
        }
        return left;
    }

    public int GetNumberOfK(int [] array , int k) {
        return rigth_bound(array,k)-left_bound(array,k);
    }

    /**==============================================================================================================================================
     * JZ4 二维数组中的查找
     * 在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
     * 从右上角开始，barget小则向下走，比target大则向左走
     * */
    public boolean Find(int target, int [][] array) {
        if (array.length==0||array[0].length==0) return false;
        int n=array.length,m=array[0].length;
        int i=0,j=m-1;
        while (i<n&&j>=0){
            if (array[i][j]==target)return true;
            else if (array[i][j]>target){
                j--;
            }else{
                i++;
            }
        }
        return false;
    }


    /**==============================================================================================================================================
     * JZ11 旋转数组的最小数字
     * 有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。
     * 请问，给定这样一个旋转数组，求数组中的最小值。
     * 二分查找，判断mid的值如果大于right，则最小元素在右边，否则在左边
     * */
    public int minNumberInRotateArray(int [] array) {
        if (array.length==1) return array[0];
        int left=0,right=array.length-1;
        while (left<right){
            int mid=left+(right-left)/2;
            if (array[mid]>array[right]){
                //左半段是递增的，最小值在右半段中
                left=mid+1;
            }else if (array[mid]==array[left]){
                right--;
            }else {
                right=mid;
            }
        }
        return array[left];
    }

    /**==============================================================================================================================================
     * JZ38 字符串的排列
     * 输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。n < 10
     * 回溯：
     * 路径：已构成的字符串
     * 选择列表：str中没有被访问到的字符
     * 终止条件：path中的字符数量等于str的长度
     * */
    ArrayList<String > res=new ArrayList<>();
    boolean[] visited=new boolean[10];
    void backtrack(char[] cs,int index,String path){
        if (index==cs.length) {
            if (!res.contains(path))
                res.add(path);
        }
        for (int i = 0; i < cs.length; i++) {
            if (!visited[i]){
                visited[i]=true;
                backtrack(cs,index+1,path+String.valueOf(cs[i]));
                visited[i]=false;
            }
        }
    }

    public ArrayList<String> Permutation(String str) {
        char[] cs = str.toCharArray();
        backtrack(cs,0,"");
        return res;
    }

    /**==============================================================================================================================================
     * JZ44 数字序列中某一位的数字
     * 数字以 0123456789101112131415... 的格式作为一个字符序列，在这个序列中第 2 位（从下标 0 开始计算）是 2 ，第 10 位是 1 ，第 13 位是 1 ，以此类题，请你输出第 n 位对应的数字。
     * 小于10，1~9，9个数字，9位
     * 小于100，10~99，90个数字，180位
     * 小于1000，100~999，900个数字，2700位
     * 各个区间的下限上限是[0,10),[10, 100),[100,1000)...位数是1，2，3...
     * 将 101112 ⋯ 中的每一位称为 数位 ，记为 n ；将 10, 11, 12, ⋯ 称为 数字 ，记为 num ；
     * 数字 10 是一个两位数，称此数字的 位数 为 2 ，记为 digit ；每 digit 位数的起始数字（即：1, 10, 100, ⋯），记为 start 。
     * 可推出各 digit 下的数位数量 count 的计算公式：count=9×start×digit
     *  */
    public int findNthDigit (int n) {
        //1、确定所求数位的所在数字的位数
        int digit=1;
        long start=1,count=9;
        while (n>count){
            n-=count;
            digit+=1;
            start*=10;
            count=digit*start*9;
        }
        //2、确定所求数位所在的数字：所求数位 在从数字 start 开始的第 [(n - 1) / digit] 个 数字 中
        long num=start+(n-1)/digit;
        //3、 确定所求数位在 num 的哪一数位：所求数位为数字 num 的第 (n - 1) \% digit 位
        return Long.toString(num).charAt((n-1)%digit)-'0';
    }
}
